package com.faiz.algorithm;

import java.util.Deque;
import java.util.LinkedList;

public class LargestRectangleArea {
    public int largestRectangleArea(int[] heights) {
        int res = Integer.MIN_VALUE;
        // 思路：通过单调栈来求解不同高度的矩形的面积
        Deque<Integer> stack = new LinkedList<>();
        for (int height : heights) {
            int count = 0;
            while (!stack.isEmpty() && stack.peek() > height) {
                count++;
                int curHeight = stack.pop();
                res = Math.max(res, curHeight * count);
            }
            stack.push(height);
        }
        // 当前栈不为空，还需要取出栈中其他高度的矩形进行计算
        int count = 0;
        while (!stack.isEmpty()) {
            count++;
            int height = stack.pop();
            res = Math.max(res, height * count);
        }
        return res;
    }

    public static void main(String[] args) {
        int[] heights = {2, 1, 2};
        LargestRectangleArea largestRectangleArea = new LargestRectangleArea();
        System.out.println(largestRectangleArea.largestRectangleArea(heights));
    }
}
